package org.example.leetCode;

import org.example.entity.TreeNode;

/**
 * 236. 二叉树的最近公共祖先
 * 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
 * <p>
 * 百度百科中最近公共祖先的定义为：
 * “对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
 */
public class Code236 {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || root == p || root == q) return root;
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        if (left == null) return right;
        if (right == null) return left;
        return root;
    }

    public static void main(String[] args) {
        Code236 solution = new Code236();

        // 构造测试二叉树:
        //       3
        //      / \
        //     5   1
        //    / \ / \
        //   6  2 0  8
        //     / \
        //    7   4

        TreeNode root = new TreeNode(3);
        TreeNode node5 = new TreeNode(5);
        TreeNode node1 = new TreeNode(1);
        TreeNode node6 = new TreeNode(6);
        TreeNode node2 = new TreeNode(2);
        TreeNode node0 = new TreeNode(0);
        TreeNode node8 = new TreeNode(8);
        TreeNode node7 = new TreeNode(7);
        TreeNode node4 = new TreeNode(4);

        root.left = node5;
        root.right = node1;
        node5.left = node6;
        node5.right = node2;
        node1.left = node0;
        node1.right = node8;
        node2.left = node7;
        node2.right = node4;

        // 测试用例1: p = 5, q = 1 => 预期结果: 3
        TreeNode result1 = solution.lowestCommonAncestor(root, node5, node1);
        System.out.println("测试用例1 - 节点5和节点1的最近公共祖先: " +
                (result1 != null ? result1.val : "null"));

        // 测试用例2: p = 5, q = 4 => 预期结果: 5
        TreeNode result2 = solution.lowestCommonAncestor(root, node5, node4);
        System.out.println("测试用例2 - 节点5和节点4的最近公共祖先: " +
                (result2 != null ? result2.val : "null"));

        // 测试用例3: p = 7, q = 4 => 预期结果: 2
        TreeNode result3 = solution.lowestCommonAncestor(root, node7, node4);
        System.out.println("测试用例3 - 节点7和节点4的最近公共祖先: " +
                (result3 != null ? result3.val : "null"));

        // 测试用例4: p = 6, q = 2 => 预期结果: 5
        TreeNode result4 = solution.lowestCommonAncestor(root, node6, node2);
        System.out.println("测试用例4 - 节点6和节点2的最近公共祖先: " +
                (result4 != null ? result4.val : "null"));

        // 测试用例5: p = 3, q = 5 => 预期结果: 3 (一个节点是另一个节点的祖先)
        TreeNode result5 = solution.lowestCommonAncestor(root, root, node5);
        System.out.println("测试用例5 - 节点3和节点5的最近公共祖先: " +
                (result5 != null ? result5.val : "null"));

        // 边界测试: 空树
        TreeNode result6 = solution.lowestCommonAncestor(null, node5, node1);
        System.out.println("边界测试 - 空树情况: " +
                (result6 != null ? result6.val : "null"));
    }
}
